Noam Chomsky creó la teoría de las gramáticas generativas, la cual es considerada una de las más significativas contribuciones al campo de la linguística teórica hecha en el siglo XX.

Cuando Noam Chomsky formalizó las gramáticas generativas en 1956, las clasificó en cuatro tipos que ahora se conocen como Jerarquía de Chomsky. Las diferencias entre los tipos de gramática es que tienen cada una reglas más restrictivas sobre las producciones y por lo que pueden generar menos lenguajes formales. Dos tipos importantes son las gramáticas independientes del contexto y las gramáticas regulares, que generan los lenguajes independientes del contexto y los lenguajes regulares respectivamente. Aunque menos poderosas que las gramáticas irrestrictas, que pueden expresar cualquier lenguaje acceptado por una máquina de Turing, estos dos tipos de gramáticas restringidas se usan con más frecuencia ya que pueden implementarse analizadores eficientes para las mismas.

Gramática Irrestricta

En la Jerarquia de Chomsky, una gramática irrestricta es una Gramatica a cuyas producciones no se le aplica ninguna restricción.

Las gramáticas irrestrictas pueden generar todos los lenguajes que pueden ser aceptados por una máquina de Turing, por lo que juegan un papel importante en la teoría de computabilidad.

Gramática Sensible al Contexto

En una Gramatica sensible al contexto, cada producción tiene la forma:

γΑβ→γωβ

donde:

Α ∈ N
γ, β ∈ (N ∪ T)^*
ω ∈ (N ∪ T)⁺

Es decir, se permite el reemplazo del no-terminal Α en el lado izquierdo de la producción por la Forma Sentencial ω sólo en el contexto γ_β. La gramática puede contener también la producción S?ε si el lenguaje que se requiere generar contiene la cadena vacía, pero solo si S no aparece en el lado derecho de alguna producción.

Definición alternativa

Otra definición de gramática sensitiva al contexto es el de la clase de gramáticas con la restricción de que para toda regla:

α→β

se cumple que:

|α| ≤ |β|

Tal gramática también se llama monotónica o no-contractiva porque ninguna e las reglas disminuye el tamaño de la Forma Sentencial que está siendo derivada.

La clase de las gramáticas no-contractivas no es exactamente igual a la de las sensitivas al contexto porque las primeras no pueden generar secuencias vacías, pero ambas clases pueden hacerse equivalentes permitiendo una producción S→ε en las gramáticas no-contractivas.

Ejemplo

L ₄ ={a ⁿ b ⁿ c ⁿ / n > 0}
G ₄ = ({A,B,C}, {a,b,c}, S4, P4)

donde P4 contiene las siguientes producciones:

1. S4→A
2. A→aABC
3. A→abC
4. CB→BC
5. bB→bb
6. bC→bc
7. cC→cc

Derivacion de la Cadena a ³ b ³ c ³:

S4 ⇒₁ A
A ⇒₂ aABC
a A BC ⇒₂ a aABC BC
aa A BCBC ⇒₃ aa abC BCBC
aaab CB CBC ⇒₄ aaab BC CBC
aaabBC CB C ⇒₄ aaabBC BC C
aaabB CB CC ⇒₄ aaabB BC CC
aaa bB BCCC ⇒₅ aaa bb BCCC
aaab bB CCC ⇒₅ aaab bb CCC
aaabb bC CC ⇒₆ aaabb bc CC
aaabbb cC C ⇒₇ aaabbb cc C
aaabbbc cC ⇒₇ aaabbbc cc

Gramática Independiente del Contexto

En una gramática independiente del contexto la parte izquierda de cada producción está formada por un único no-terminal.

Α→β
Α ∈ N
β ∈ (T ∪ N)^*

Suele abreviarse la clase de las gramáticas independientes del contexto con las siglas CFG por su nombre en inglés (Context Free Grammar).

La clase de las gramáticas independientes del contexto es un subconjunto de la de las gramáticas sensibles al contexto.

La mayoría de los lenguajes de programación pueden ser generados por gramáticas independientes del contexto.

Ejemplos

El Lenguaje Generado por la Gramatica del primer ejemplo de la definición de gramáticas sensibles al contexto. {a ⁿ b ⁿ c ⁿ }, no puede ser generado por una gramática independiente del contexto.

En cambio el lenguaje:

L = {wcw ^R | w ∈ {a,b} }

puede ser generado por una Gramatica con las siguientes producciones:

S→A;
A→aAa
A→bAb;
A→c

Gramatica Regular

En una gramática regular (o gramática lineal), el lado izquierdo es restringido a un único símbolo no-terminal (tal como en una gramática independiente de contexto) y el lado derecho es restringido a:

• A→ε, la cadena vacía
• A→a, con a ∈ Σ, un elemento del alfabeto subyacente

o a:

• A→aB, con a ∈ Σ, B ∈ N

para gramáticas lineales derechas, o a:

• A→Ba, con a ∈ Σ, B ∈ N

para las gramáticas lineales izquierdas.

Las gramáticas lineales izquierdas y derechas son ambas gramáticas regulares.

Las gramáticas regulares generan los lenguajes regulares, que es la misma clase de lenguajes definida por los conjuntos regulares, las expresiones regulares, y los automatas finitos.

Las gramáticas regulares son un subconjunto de la clase de las gramáticas independientes del contexto.

Ejemplos

Las siguientes gramáticas, G ₁ y G ₁, son gramáticas regulares lineal derecha y lineales izquierda respectivamente que generan el lenguaje L = {a ²ⁿ | n ≥ 0}.

S ₁→ε
S ₁→aA
A→aB
A→a
B→aA

S ₂→ε
S ₂→aC
C→Da
C→a
D→Ca